10.0 KB · ⇊ 4 parts · ⤓ Micron 10.0 KB · ⤓ HTML 50.2 KB

top

Un mwbamultiinsieme, in mwbqmatematica, e più in particolare nella mwbgcombinatoria, nella mwbwlogica matematica e nella mwcateoria degli insiemi, è una generalizzazione del concetto basilare di mwcqinsieme. Potrebbe definirsi con un elenco che ammette elementi ripetuti: si potrebbe ad esempio rappresentare con un elenco come mwcg a , a , a , b , b , c {\displaystyle a,a,a,b,b,c} . Una tale collezione, infatti, non corrisponde alla concezione prevalente di insieme come collezione di elementi tutti distinti tra loro. Ma nella definizione di multiinsieme, a differenza di quello che accade per un elenco o una lista, non è rilevante l'ordine in cui compaiono gli elementi.

Formalmente, un multiinsieme è definito come una coppia mwda M = ( A , m ) {\displaystyle M=(A,m)} , dove mwdq A {\displaystyle A} è un insieme e mwdg m : : A → → N ∗ ∗ {\displaystyle m\colon A\rightarrow \mathbb {N} ^{*}} è una mwdwfunzione a valori mweanaturali positivi; mweq A {\displaystyle A} viene detto insieme mwegsupporto del multiinsieme, i suoi elementi si dicono mwewelementi del multiinsieme ed mwfa m {\displaystyle m} mwfqmolteplicità del multiinsieme. Si può dire che la funzione molteplicità associa ad ogni elemento del multiinsieme un mwfgnumero di ripetizioni che costituiscono il multiinsieme stesso; per esempio nel caso sopra menzionato si ha:

• mwgq m ( a ) = 3 , {\displaystyle m(a)=3,}

• mwgw m ( b ) = 2 , {\displaystyle m(b)=2,}

• mwhq m ( c ) = 1. {\displaystyle m(c)=1.}

Si osservi che la sola funzione molteplicità individua completamente un multiinsieme: in effetti la nozione può ridursi a quella di funzione a valori interi positivi e per un generico multiinsieme, ricorrendo alla nozione di mwhwdominio, si può scrivere mwia ( A , m ) = ( d o m ( m ) , m ) {\displaystyle (A,m)=(\mathrm {dom} (m),m)} .

La somma dei numeri di ripetizioni esprime il numero delle coppie costituenti la funzione mwig m {\displaystyle m} e quindi viene detta mwiwcardinalità del multinsieme.

Risulta utile servirsi dei termini e delle notazioni dei multiinsiemi per ragioni di pratica espositiva, come accade per i due primi esempi del paragrafo che segue e in varie questioni enumerative nella mwjqcombinatoria e nella mwjgteoria dei gruppi.

Da quanto detto si evince in modo esplicito che se l'insieme mwkaimmagine di mwkq m {\displaystyle m} (ossia l'insieme dei valori assunti da mwkg m {\displaystyle m} ) coincide con l'insieme mwkw { 1 } {\displaystyle \{1\}} , allora il multiinsieme si può confondere con il suo insieme sostegno.

Naturalmente, dato che ogni funzione si può presentare come insieme di coppie, ogni multiinsieme mwlq M = ( A , m ) {\displaystyle M=(A,m)} può essere presentato come l'insieme delle mwlgcoppie ordinate mwlw { ( a , m ( a ) ) : a ∈ ∈ A } {\displaystyle \{(a,m(a)):a\in A\}} ; nell'esempio iniziale: mwma M = { ( a , 3 ) , ( b , 2 ) , ( c , 1 ) } {\displaystyle M=\{(a,3),(b,2),(c,1)\}} .

Il numero dei multinsiemi di cardinalità mwmg k {\displaystyle k} di un insieme mwmw A {\displaystyle A} di cardinalità mwna n {\displaystyle n} è dato dal mwnqcoefficiente binomiale mwng ( k − − 1 n − − 1 ) {\displaystyle {k-1 \choose n-1}} ; è quindi uguale al numero delle mwnwcomposizioni di mwoa k {\displaystyle k} in mwoq n {\displaystyle n} parti.

Se si specifica un universo mwpq U {\displaystyle U} di cui mwpg A {\displaystyle A} sia sottoinsieme, la definizione di funzione molteplicità diviene mwpw m u : : U → → N {\displaystyle m_{u}\colon U\rightarrow \mathbb {N} } ; in tal caso, la molteplicità degli elementi di mwqa U {\displaystyle U} non appartenenti ad mwqq A {\displaystyle A} è nulla.

Il numero di tali multinsiemi di cardinalità mwqw k {\displaystyle k} di un insieme mwra U {\displaystyle U} di cardinalità mwrq n {\displaystyle n} viene detto, nella terminologia combinatoria classica, numero delle mwrgcombinazioni con ripetizione di mwrw n {\displaystyle n} oggetti di classe mwsa k {\displaystyle k} .

La funzione molteplicità mwsg m u : : U → → N {\displaystyle m_{u}\colon U\rightarrow \mathbb {N} } generalizza la mwswfunzione indicatrice di un insieme, quest'ultima essendo vincolata ad assumere solo i valori 0 o 1.

• Esempi

• Voci correlate

• Collegamenti esterni

La nozione di multiinsieme serve per individuare con chiarezza la collezione dei mwtgfattori primi di un dato numero naturale. Se per esempio si osserva che mwtw 720 = 2 4 3 2 5 {\displaystyle 720=2^{4}3^{2}5} , si può affermare che il multiinsieme dei fattori primi di 720 è mwua A = { ( 2 , 4 ) , ( 3 , 2 ) , ( 5 , 1 ) } {\displaystyle A=\{(2,4),(3,2),(5,1)\}} . Un altro esempio è dato dalle mwuqradici di un mwugpolinomio; ad esempio le radici del polinomio mwuw x 3 − − 5 x 2 + 7 x − − 3 {\displaystyle x^{3}-5x^{2}+7x-3} costituiscono il multiinsieme mwva { ( 1 , 2 ) , ( 3 , 1 ) } {\displaystyle \{(1,2),(3,1)\}} .

Si osservi che nei due esempi precedenti, parlando di multiinsiemi si hanno enunciati piuttosto chiari e si evitano discorsi nei quali si usa a sproposito il termine insieme.

Nella pratica spesso un multiinsieme viene efficacemente individuato con una notazione esponenziale che si richiama alla fattorizzazione degli interi: per l'esempio del polinomio si potrebbe scrivere mwvw { radici di x 3 − − 5 x 2 + 7 x − − 3 } = 1 2 3 1 {\displaystyle \{{\text{radici di }}x^{3}-5x^{2}+7x-3\}=1^{2}3^{1}} . Anche per questa notazione si conviene di evitare di scrivere gli esponenti uguali a 1. Talora un multiinsieme viene presentato con un mwwaistogramma formato da colonne di quadratini uguali sovrapposti.

Si potrebbero trattare anche multiinsiemi aventi come sostegno un insieme infinito: in effetti una mwwgsuccessione di interi (come la mwwwsuccessione di Fibonacci o la successione dei mwxanumeri di Catalan) potrebbe considerarsi un multiinsieme. Di solito però si considerano solo multiinsiemi con sostegno finito.

• mwyaCombinazione

• mwygInsieme

• mwzaFunzione indicatrice

• mwzgInsieme sfocato

• mwaaLista (informatica)

• citerefmathworld(EN) Eric W. Weisstein, Multiset, su MathWorld, Wolfram Research.